#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

  Definition for singly-linked list.
  struct ListNode {
      int val;
      struct ListNode *next;
  };
 
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    ListNode* cur = head;
    ListNode* prev = NULL;
    while (cur) {
        ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}


bool isPalindrome(struct ListNode* head) {
    if (!head || !head->next)
        return true;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    ListNode* l1 = head;
    ListNode* l2 = reverseList(&slow);
    while (l2)
    {
        if (l1->val != l2->val)
            return false;
        l1 = l1->next;
        l2 = l2->next;
    }
    return true;
}